package BFS解决FloodFill算法;

import java.util.LinkedList;
import java.util.Queue;

public class 岛屿数量 {

    int [] dx = {0,0,-1,1};
    int [] dy = {1,-1,0,0};
    boolean [][] vis = new boolean[301][301];
    int m,n;
    public void numIslands(char [][] grid)
    {
        m = grid.length;
        n = grid[0].length;
        int count = 0;
        for(int i = 0 ; i < m ; i++)
        {
            for(int j = 0 ; j < n ; j++)
            {
                if(grid[i][j] == '1' && !vis[i][j])
                {
                    bfs(grid,i,j);
                    count++;
               }
            }
        }
    }

    public void bfs(char[][] grid,int i,int j)
    {
        Queue<int[]> q= new LinkedList<>();
        q.add(new int []{i,j});
        vis[i][j] = true;
        while(!q.isEmpty())
        {
            int [] t = q.poll();
            int a = t[0],b = t[1];
            for(int d = 0 ; d < 4 ; d++)
            {
                int x = a+dx[d];
                int y = b+dy[d];
                if(x>=0 && x<m && y>=0 && y<n && grid[x][y] == '1' && !vis[x][y])
                {
                    q.add(new int []{x,y});
                    vis[x][y] = true;
                }
            }
        }
    }


    // 方法二：
//    public int numIslands(char [][] grid)
//    {
//        int count = 0;
//        int m = grid.length;
//        int n = grid[0].length;
//        Queue<int[]> q = new LinkedList<>();
//        for(int i = 0 ;i < m ; i++)
//        {
//            for(int j = 0 ; j<n ;j++)
//            {
//                if(grid[i][j] == '1')
//                {
//                    q.add(new int []{i,j}) ;
//                }
//            }
//        }
//
//        while(!q.isEmpty())
//        {
//            int [] cur = q.poll();
//            for(int i = 0 ; i < 4 ; i++)
//            {
//                int x = cur[0]+dx[i];
//                int y = cur[1]+dy[i];
//
//                if(x>=0 && x<m && y>=0 && y<n && grid[x][y] == '1')
//                {
//                    grid[x][y] = '0';
//
//                }
//            }
//            count++;
//        }
//        return count;
//    }
}
